"""
通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

"""
def quickSort(array,left,right,):
    if left<right:
        pi =partion(array,left,right)
        quickSort(array,left,pi-1)
        quickSort(array,pi+1,right)

# 排序后寻找最中间的值
def partion(arr,low,righ):
    i=low-1 # 最小元素索引
    pivot=arr[righ]  #最末尾的数
    for j in range(low,righ):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i+=1
            # 交换数据
            arr[i],arr[j]=arr[j],arr[i]
    # 将中间值放在中间
    arr[i+1], arr[righ] = arr[righ], arr[i+1]
    return i+1



if __name__ == "__main__":
    array = [3, 2, 1,8,55,43,2,1,0]
    quickSort(array,0,len(array)-1)
    print(array)